Phó tế Nguyễn Văn Long được thụ phong linh mục ngày 30 tháng 12 năm 1989, bởi Giám mục George Pell, giám mục phụ tá Tổng giáo phận Melbourne.[1] Sau khi được truyền chức linh mục, vị linh mục trẻ tuổi được bổ nhiệm làm phó xứ Giáo xứ Springvale. Hai năm sau đó, ông được cử đến Roma du học và nhận bằng Cao học thần học tu đức và bằng Kitô học năm 1994 tại Học viện Seraphicum của dòng Anh Em Hèn Mọn Viện Tu.[14] Ông cảm thấy ấn tượng trải nghiệm sống chung với nhiều giáo sĩ đến từ các quốc gia khác nhau trên thế giới. Ông cảm nhận đó là tính phổ quát của Giáo hội Công gaío Rôma, một trật tự hoạt động tuy hỗn loạn nhưng có sức hấp dẫn riêng.[9]

Trở về Úc, linh mục Vinh Sơn Long được bổ làm Giám đốc thỉnh sinh của nhà dòng tại Úc và đảm nhiệm cương vị này đến năm 1998. Năm 1999, ông được bổ nhiệm làm linh mục chính xứ giáo xứ Kellyville, bang New South Wales, Giáo phận Parramatta.[14] Tính đến thời điểm này, ông vẫn là linh mục người Úc gốc Việt Nam đầu tiên. Giáo xứ Kellyville hầu như không có giáo dân gốc Việt. Với việc quản lý giáo xứ này, linh mục Long đã thực hiện các công tác mục vụ khi giáo xứ gặp tình trạng "bùng nổ dân số": nhiều gia đình cần chào đón, nâng cấp hoặc xây mới các cơ sở như nhà thờ và trường học,... Ngày ông rời giáo xứ là ngày thánh hiến trung tâm mục vụ mới vừa hoàn thành.[9]

Năm 2002, linh mục Vinh Sơn Long được điều chuyển làm linh mục chính xứ giáo xứ Springvale và đảm nhận cương vị này cho đến năm 2005.[14] Giáo xứ này chủ yếu là người gốc Á và tỉ lệ dự thánh lễ Công giáo cao. Linh mục Long cho rằng vấn đề mục vụ khó nhất tại đâ là tạo sự hài hòa trong đa dạng, tránh thiên vị.[9] Song song với các chức vị trên, trong giai đoạn từ năm 1995 đến năm 2005, ông là Tổng thủ quyền dòng Anh Em Hèn Mọn Australia (Dòng Phanxicô) và từ năm 2005 đến năm 2008 là giám tỉnh dòng Anh Em Hèn Mọn Australia. Song song với thời gian đảm nhận vai trò Giám tỉnh dòng tại Úc, ông kiêm nhiệm chức Chủ tịch Dòng Phanxicô tại Châu Á - Úc.[14][15]

Từ năm 2008 đến năm 2011, ông là thành Viên Tổng Quyền Quốc Tế của Dòng Phanxicô, cư trú tại Nhà Tổng Quyền Roma.[14] Từ ngày 22 tháng 4 năm 2008, ông là Tổng cố vấn dòng Anh Em Hèn Mọn, là tu sĩ đặc trách vùng châu Á - Thái Bình Dương (FAAMC).[12]